package leetCode.function;

import javax.annotation.processing.SupportedSourceVersion;

import com.alibaba.fastjson.JSON;

/**
 * @author jerry
 * @ClassName:  NQueen   
 * @Description: N皇后问题最优解   
 * @date 2023年12月6日 下午5:13:37
 */
public class NQueen {

	public static void main(String[] args) {
		long start1 = System.currentTimeMillis();
		System.out.println(new NQueen().getNQueen1(14) + " " + (System.currentTimeMillis()-start1));
		long start2 = System.currentTimeMillis();
		System.out.println(new NQueen().getNQueen2(14) + " " + (System.currentTimeMillis()-start2));
	}

	// 位运算，比暴力递归优化了常数项，时间复杂度依然为N!
	public int getNQueen1(int n) {
		int res = 0;

		int limit = n == 32 ? -1 : ((1 << n) - 1), colLimit = 0, leftLimit = 0, rightLimit = 0;
		res = process1(n, limit, colLimit, leftLimit, rightLimit);
		return res;
	}

	private int process1(int n, int limit, int colLimit, int leftLimit, int rightLimit) {
		int res = 0;
		if (limit == colLimit) {
			return 1;
		}
		int testSite = limit & (~(colLimit | leftLimit | rightLimit));
		while (testSite != 0) {
			int mostRightOne = testSite & ((~testSite) + 1);
			testSite ^= mostRightOne;
			res += process1(n, limit, colLimit | mostRightOne, (leftLimit | mostRightOne) << 1,
					(rightLimit | mostRightOne) >> 1);
		}
		return res;
	}

	// 暴力递归
	public int getNQueen2(int n) {
		int res = 0;
		res = process2(n, 0, new int[n]);
		return res;
	}

	// 用i表示当前第几行，用j=arr[i]表示i行j列
	public int process2(int n, int i, int[] arr) {
		if (i == n) {
			return 1;
		}
		int res = 0;
		for (int j = 0; j < n; j++) {
			if (isValid(arr, j, i)) {
				arr[i] = j;
				res += process2(n, i + 1, arr);
			}
		}
		return res;
	}

	private boolean isValid(int[] arr, int j, int i) {
		for (int k = 0; k < i; k++) {
			if (arr[k] == j || Math.abs(arr[k] - j) == Math.abs(i - k)) {
				return false;
			}
		}
		return true;
	}
}
